/*global pi */
pi.mod.define('pi.scene.nav', function (pi) {
	"use strict";

	var module = {};

	/** 从配置创建导航对象 */
	module.create = function (obstacles, query) {
		var nav = {}, // 导航对象
			navNet, // 网络数据
			creatNetFun = function () {
				var i, j, ptno, pt, npt, obs, dx, dz, dist, net = {};

				ptno = 0;
				net.pts = [];
				for (i = 0; i < obstacles.length; i++) {
					obs = obstacles[i];
					for (j = 0; j < obs.polygon.length; j++) {
						pt = obs.polygon[j];
						pt.no = ptno++;
						pt.x += obs.pos.x;
						pt.z += obs.pos.z;
						pt.y = 0.5;
						net[pt.no] = {};
						net.pts.push(pt);
					}
				}

				// 建立基本的连通网络
				for (i = 0; i < net.pts.length; i++) {
					net[i][i] = 0;
					for (j = i + 1; j < net.pts.length; j++) {
						pt = net.pts[i];
						npt = net.pts[j];
						if (query.doQuery(pt, npt, false).length === 0) {
							dx = npt.x - pt.x;
							dz = npt.z - pt.z;
							dist = Math.sqrt(dx * dx + dz * dz);
							net[i][j] = dist;
							net[j][i] = dist;
						}
					}
				}

				return net;
			};

		/** 获取所有障碍信息 */
		nav.getAllObstacles = function () {
			return obstacles;
		};

		/** 获取导航网络 */
		nav.getNavNet = function () {
			if (navNet === undefined) {
				navNet = creatNetFun();
			}
			return navNet;
		};

		/** 搜索路径 */
		nav.findPath = function (start, end) {
			var i, j, pt, npt, dx, dz, dist, minDist, loop,
				midPts = {},
				setS = [],
				setE = [],
				net = nav.getNavNet(),
				path = [],
				startTime;

			// 如果起始点直接可达，就不用寻路了
			if (query.doQuery(start, end, false).length === 0) {
				return [start, end];
			}

			startTime = pi.lang.createDate().getTime();

			// 将 start 和 end 加入导航网络
			start.no = net.pts.length;
			end.no = start.no + 1;
			net[start.no] = {};
			net[end.no] = {};

			npt = start;
			for (i = 0; i < net.pts.length; i++) {
				pt = net.pts[i];
				if (query.doQuery(pt, npt, false).length === 0) {
					dx = npt.x - pt.x;
					dz = npt.z - pt.z;
					dist = Math.sqrt(dx * dx + dz * dz);
					net[i][npt.no] = dist;
					net[npt.no][i] = dist;
				}
			}

			npt = end;
			for (i = 0; i < net.pts.length; i++) {
				pt = net.pts[i];
				if (query.doQuery(pt, npt, false).length === 0) {
					dx = npt.x - pt.x;
					dz = npt.z - pt.z;
					dist = Math.sqrt(dx * dx + dz * dz);
					net[i][npt.no] = dist;
					net[npt.no][i] = dist;
				}
			}

			pi.log("pathfinding - create net: " + (pi.lang.createDate().getTime() - startTime) + " ms");
			startTime = pi.lang.createDate().getTime();

			// 开始 Dijkstra 搜索最短路径
			setE = setE.concat(net.pts);
			setE.push(end);
			loop = true;
			while (loop) {
				minDist = {};
				loop = false;
				for (i = 0; i < setE.length; i++) {
					pt = setE[i];
					dist = net[start.no][pt.no];

					if (dist !== undefined && (minDist.dist === undefined || dist < minDist.dist)) {
						minDist.dist = dist;
						minDist.pt = pt;
						minDist.mid = undefined;
					}

					for (j = 0; j < setS.length; j++) {
						npt = setS[j].pt;
						if (net[pt.no][npt.no] !== undefined) {
							dist = net[pt.no][npt.no] + setS[j].dist;
							if (minDist.dist === undefined || dist < minDist.dist) {
								minDist.dist = dist;
								minDist.pt = pt;
								minDist.mid = npt;
							}
						}
					}
				}

				if (minDist.dist !== undefined) {
					loop = true;
					setS.push({pt: minDist.pt, dist: minDist.dist});
					setE.splice(setE.indexOf(minDist.pt), 1);
					if (minDist.mid !== undefined) {
						midPts[minDist.pt.no] = minDist.mid;
					}
				}

				if (minDist.pt === end) {
					pt = end;
					while (pt !== undefined && pt !== start) {
						path.push(pt);
						pt = midPts[pt.no];
					}
					path.push(start);
					break;
				}
			}

			// 从网络中将起始点清除 
			for (i = 0; i < net.pts.length; i++) {
				pt = net.pts[i];
				if (net[pt.no][start.no] !== undefined) {
					net[pt.no][start.no] = undefined;
					net[start.no][pt.no] = undefined;
				}
				if (net[pt.no][end.no] !== undefined) {
					net[pt.no][end.no] = undefined;
					net[end.no][pt.no] = undefined;
				}
			}

			pi.log("pathfinding - dijkstra: " + (pi.lang.createDate().getTime() - startTime) + " ms");

			return path;
		};

		return nav;
	};

	return module;
});
